/*
 * @Author: liusheng
 * @Date: 2022-07-11 21:55:27
 * @LastEditors: liusheng
 * @LastEditTime: 2022-07-11 21:55:31
 * @Description: 剑指 Offer II 097. 子序列的数目
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 097. 子序列的数目
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

 

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag
 

提示：

0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
 

注意：本题与主站 115 题相同： https://leetcode-cn.com/problems/distinct-subsequences/

通过次数7,479 提交次数13,530
 */

#include "header.h"
class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size();
        int n = t.size();
        if (m < n)
        {
            return 0;
        }

        /*
        设 f(i, j) 表示字符串 s 下标从 i 到末尾的字符串 中等于
        字符串 t 下标从j 到末尾的子字符串的子序列个数
        当 j=n 时，t[j:为空字符串，由于空字符串是任何字符串的子序列，因此对任意 0≤i≤m，有 dp[i][n]=1；
        */
        vector<vector<unsigned long long>> dp(m + 1,vector<unsigned long long>(n + 1,0));
        for (int i = 0; i <= m; ++i)
        {
            dp[i][n] = 1;
        }

        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                if (s[i] == t[j])
                {
                    dp[i][j] = dp[i+1][j+1] + dp[i + 1][j];
                }
                else
                {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }

        return dp[0][0];
    }
};
